Routing is elementary in all communication networks. Such routing involves transmitting network data traffic among the devices that communicate together and comprise nodes of the network. The design of routing algorithms is tightly coupled with the design of auxiliary infrastructure that abstracts the network connectivity. For networks with stable links and powerful nodes, such as the Internet, infrastructures such as routing tables are constructed and maintained so that routing can be performed efficiently at each router by a routing table look-up, and routing paths are close to optimum. For networks with fragile links, constantly changing topology, and nodes with less resourceful hardware, such as ad hoc mobile wireless networks, routing tends to be infrastructure-less and on-demand. However, without any auxiliary infrastructure, discovery of routes in such wireless networks may have to rely on flooding the network.
Flooding involves the broadcast of flood message packets across the network so that each node receiving a packet will rebroadcast that packet on links other than the receiving link. A network path query can be solved in this way, so that when a destination node receives the flood packet, it can report the path that was traversed, thereby identifying a network route from the original sending node to the destination node. Flooding can result in redundant rebroadcast of flood messages. This unnecessarily increases network traffic and increases node energy consumption. As a result, efficient routing is of great concern for those who are involved with planning for wireless networks.
One type of wireless network is the wireless sensor network. Such networks typically include many autonomous, battery-powered communication devices that include environmental sensors for collection of data and radio frequency transceivers for network communications and data transfer. Network routing is important because nodes may need to share information among themselves or may need to move data from an originating node to a destination node. In wireless sensor networks, where sensor nodes are movable but generally stationary and are deployed in a geometric space, each sensor node has a constrained power supply, and thus energy conservation is an important consideration in the design of routing protocols. Reactive routing protocols, which are designed mainly for ad hoc mobile wireless networks and rely on flooding for route discovery, are typically much too energy-expensive for sensor networks. It is also observed that wireless links for static sensor nodes, such as Berkeley motes, are reasonably stable. Therefore it is advantageous to preprocess the network and maintain some lightweight infrastructure so that efficient and localized routing can be performed.
A good intuition on how to build a lightweight and effective auxiliary infrastructure is that sensor networks are closely related to the geometric environment in which they are deployed. Two nodes can directly communicate when they are geographically close. Thus geometric proximity information has high correlation with network topology. This intuition has been used in geographical forwarding, which is used to efficiently and effectively make routing decisions based on the geographical locations of destinations and the one-hop neighboring nodes. In geographical forwarding, a packet is greedily forwarded to the one-hop neighbor that is geographically closest in position to the destination. Such an abstraction of the network connectivity based on the Euclidean coordinates of a node has tremendously simplified the design of routing protocols and improved routing efficiency. For a sensor network with uniform and dense sensor deployment in a flat and regular region, geographical forwarding has been found to be an efficient and scalable scheme that produces almost shortest paths with very little overhead.
An issue on the practicality of geographical routing is how to obtain the geographical locations of a large number of sensor nodes. An essential part of the preprocessing overhead of building the infrastructure for geographical routing is to solve the localization problem, namely, finding the Euclidean coordinates of the sensor nodes. Localization to physical coordinates can be achieved by either hardware support such as Global Positioning Systems (GPS), or by algorithms that determine the locations of sensor nodes from their local interactions. In fact, if sensors are densely deployed in a flat regular region with simple geometry (e.g., a disk with no holes), then greedy geographical routing is robust enough to localization errors, and approximate locations suffice. See, for example, A. Rao et al., in Proceedings of the 9th annual international conference on Mobile computing and networking, pages 96-108, ACM Press (2003); J. Bruck et al. in Proc. 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), May 2005.
The greedy geographical forwarding, however, runs into serious problems for sensor fields with complex geometry. In many of the real-world situations where sensor networks are deployed, such as metropolitan areas, warehouses, university campuses, and airport terminals, the sensor field naturally has a complex shape and can have many holes (regions where sensors are not deployed due to the existence of obstacles). When there are holes in a sensor field, greedy forwarding can fail when all the neighbors are further away from the destination. In other words, a route created by greedy forwarding tries to follow a straight line from source to destination, which is often blocked by obstacles in a complex environment. A number of ways have been devised to get around holes. For example, face routing or perimeter routing deals with this case by routing a packet along the face of a planar subgraph until greedy forwarding can be performed again. See B. Karp and H. Kung, in Proc. of the ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), pages 243-254 (2000); P. Bose et al., in 3rd Int. Workshop on Discrete Algorithms and methods for mobile computing and communications (DialM 99), pages 48-55 (1999).
If the sensor network has rich geometric features, perimeter routing has to be adopted frequently. There are several issues with face routing or perimeter routing. The correct construction of the planar subgraph depends heavily on accurate location information, which is very hard to obtain, and the assumption that the communication graph is a unit disk graph, which does not hold in practice. See, for example, D. Ganesan et al., Complex behavior at scale: An experimental study of low-power wireless sensor networks; Technical Report UCLA/CSD-TR 02-0013, UCLA (2002). Inaccurate location information or a slight deviation of the communication graph from the unit disk graph model may cause the planar subgraph to be disconnected. See, for example, K. Seada et al., in IPSN'04: Proceedings of the third international symposium on Information processing in sensor networks, pages 71-80, ACM Press (2004). Further, perimeter routing creates awkward routing paths along the boundaries of holes. Overloading of nodes on the boundaries of holes exhausts the batteries of those nodes quickly, which will further enlarge the holes and eventually connect small holes to big holes or even disconnect the network.
The failure of greedy forwarding for sensor fields with complex geometry and/or non-trivial topology occurs mainly because the geographical location information, on which routing rules are based, does not correlate well with the connectivity graph. Two nodes that are geographically close may actually be far away in the connectivity graph. A good infrastructure for this case should not only abstract the geometric proximity of the sensors, but also the global geometric shape and topological features of the sensor field. This intuition is validated by the observation that the global shape and the topological features of the layout mostly reflect the underlying structure of the environment (e.g. obstacles), and they are likely to remain stable. Nodes/links may come and go. But only when such changes are of large quantity and geographically correlated, can they possibly modify the global shape of the sensor field, or destroy/create large-scale topological features. Thus we can afford to explicitly compute an abstraction of the geometry of sensors and carry out proactive routing at this abstract level, such that these high-level combinatorial routes can be efficiently realized in the network by localized and decentralized protocols.
A protocol that explicitly states the importance of topological information in routing in sensor networks with large holes, called GLIDER, was recently proposed by Fang et al. See Q. Fang et al., in Proc. of the 24th Conference of the IEEE Communication Society (INFOCOM), March 2005. GLIDER is a naming and routing scheme based on geographical landmarks, where the global topology of the network is represented by a compact abstract Delaunay triangulation on a set of landmarks, and is used in a global planning step to guide routes around holes. However, the performance of landmark-based routing algorithms heavily depends on the selection of landmarks; yet there is currently no theoretical understanding on how to select a good set of landmarks. Moreover, landmark-based routing depends on network nodes knowing their position relative to the landmarks, which can require complicated processing and communications resources. In addition, such routing sometimes depends on a set of stable, fixed physical locations within the sensor field. Any disruption to the landmark locations will cause the routing to fail. Increasing the size of the sensor network can require finding new landmarks, which can constrain scalability.
From the discussion above, it should be apparent that there is a need for a routing scheme for wireless networks that is resource efficient, independent of location information, and has good scalability. The present invention satisfies this need.